The Internet communication has experienced an exponential speed boost, and it is very important to forward packets in wire-speed of the packets coming into routers. In response, many algorithms have been developed to enhance the router performance, which may be evaluated by certain measures. A first performance measure being used is the number of memory accesses required at the time of the address lookup to a routing table stored in the router. To speed up the packet forwarding, searching for forwarding information with fewer memory accesses is desirable. A second measure is the size of the memorized routing table in the router. The table is desirably constructed to store as many prefixes as possible effectively in the limited router memory. This depends upon the data structure of the IP address lookup algorithm. A third measure is the readiness of data updates by adding or deleting prefix information of the networks connecting the router. Actually, a huge number of prefixes per second are being renewed and deleted. So, it is important to accommodate such information in real time to go through an accurate searching. A fourth measure is the extensibility of the addressing scheme from the Internet Protocol version 4 (IPv4) to version 6 (IPv6). The current popular IPv4 address family has been exhausted and the transition became necessary to the almost infinite Internet addresses available through IPv6. Thus, it is a must to accommodate this change.
In the past, address lookup has been performed according to “Exact Matching” procedures by using the address family with classes. A classless inter-domain routing (CIDR), however, is currently under popular use to prevent the prefixes from being wasted. The CIDR allows the construction of variously sized networks depending on the number of hosts connected to the networks. On the flip side, the CIDR requires prefixes created in various lengths which make the procedures of the Internet address lookup very complex in switching systems such as routers. A prefix length is the network part of the destination address of an input packet. Not knowing the prefix length in advance, with respect to each input packet it is possible for the router to contain a number of matching prefixes of which the longest matching prefix (LMP) becomes the best matching prefix (BMP).
There have been efforts to find an effective IP address lookup architecture that satisfies the above described router performance measures and meets the address scheme change. Many researches on IP address lookup architectures have yielded tree architecture-based algorithms, hashing-based algorithms, and Bloom filter-based algorithms.
Among the conventional tree architecture-based algorithms, a binary trie (B-Trie) algorithm stores information in matching nodes by way of each bit value of the prefix. This algorithm starts searching from the most significant bit of the prefix as it checks through the respective bit values from the root of the tree. The binary trie algorithm is simple in architecture but has a disadvantage of having many empty nodes. This in turn has a huge memory demand and has a downside with respect to lookup speed because searching has to proceed linearly to the maximum length of the prefix in the worst case scenario to thereby critically deteriorate the searching performance.
In addition, among the conventional tree architecture-based algorithms, a binary search tree (BST) algorithm has less memory demand for its lack of empty nodes unlike the binary trie algorithm. This algorithm, however, needs a binary lookup tree to be structured reflecting nesting relations of the prefix and thus the structural unbalance will become worsen, depending on the degree of nesting causing deterioration in the search performance.
In addition, among the conventional hashing-based algorithms, a parallel hashing architecture algorithm has separate hashing hardware, main tables and sub-tables in each prefix length. According to the algorithm, every table is stored in the individual SRAMs making the search carried out by allowing parallel access to each table. In this algorithm, the longest table output goes through as the final search result in a priority encoder.
Such a parallel hashing architecture algorithm allows parallel access to each table and in turn provides a fast search only at the cost of more hardware and memory resources. Moreover, hardware structuring is supposed to be specified for each routing group, making its software equivalence can not be readily achieved with necessary flexibility.
Lastly, a conventional Bloom filter-based algorithm constructs Bloom filters by prefix length for filtering an input value by using a bit-vector by checking whether it is an element of a specified set. The thus reduced number of accesses to the hash table through the Bloom filter improves the search performance. The prefix length-specific construction of the Bloom filters, however, causes a highly complex architecture.
To summarize, various prior art IP address lookup architectures have failed to either satisfy such requirements as the router performance measures or to provide a handsome to meet the changing need in the transition of the address lookup schemes.